/*
 ============================================================================
 Name        : merge_sort.c
 Author      : Yineng Chen
 Version     : 1.0
 Time        : 2011-10-04
 Description : Merge sort
 ============================================================================
 */

#include <stdio.h>
#include <limits.h>

void merge_v1(int data[],int p,int q,int r)
{
	int temp[r-p+1];
	int i=p,j=q+1,k=0;
	for(;;)
	{
		if(i>q&&j>r)
		{
			break;
		}
		else if(i>q&&j<=r)
		{
			temp[k]=data[j];
			++j;
			++k;
		}
		else if(i<=q&&j>r)
		{
			temp[k]=data[i];
			++i;
			++k;
		}
		else
		{
			if(data[i]<=data[j])
			{
				temp[k]=data[i];
				++i;
			}
			else
			{
				temp[k]=data[j];
				++j;
			}
			++k;
		}
	}
	for(k=0;k<r-p+1;++k)
	{
		data[p+k]=temp[k];
	}
}

void merge_v2(int data[],int p,int q,int r)
{
	int Ldata[q-p+1+1];
	int Rdata[r-q+1];
	int i=0,j=0,k=0;

	for(i=0;i<q-p+1;++i)
	{
		Ldata[i]=data[p+i];
	}
	Ldata[i]=INT_MAX;
	for(i=0;i<r-q;++i)
	{
		Rdata[i]=data[q+1+i];
	}
	Rdata[i]=INT_MAX;//MAX_NUM;
	for(i=p,j=0,k=0;i<=r;++i)
	{
		if(Ldata[j]<=Rdata[k])
		{
			data[i]=Ldata[j];
			++j;
		}
		else
		{
			data[i]=Rdata[k];
			++k;
		}
	}
}

void merge_sort(int data[],int p,int r)
{
	int q=0;

	if(p<r)
	{
		q=(p+r)/2;
		merge_sort(data,p,q);
		merge_sort(data,q+1,r);
		merge_v2(data,p,q,r);
	}
}

int main(void)
{
	printf("merge_sort.c\n");
	int a[10]={6,35,7,9,1,2,7,43,8,3};
	int i=0;

	merge_sort(a,0,9);

	for(i=0;i<10;++i)
	{
		printf("%d ",a[i]);
	}
	return 0;
}
